自分は 黄金分割探索 をよく知りませんが、↓こちらの記事を参考に書き換えてみました。
三分探索の次の2行のみを書き換え(でAC)
double c1 = (l * gold + r) / (1.0 + gold);
double c2 = (l + r * gold) / (1.0 + gold);
Like!
競技プログラミングの初心者です。
ARC054B - ムーアの法則を解きました。三分探索を使ったコードではACできましたが、三分探索より効率の良い方法として黄金分割探索があることをネットで知り、そちらでも解いてみたいと思いました。
しかし、書いてみたコードでは入力に対して期待されるものとは異なるものが出力されてしまいます。ChatGPTに聞いてみるなどしたのですが解決できませんでした。原因を教えてほしいです。
三分探索でACしたコードも載せておきました。
#include <bits/stdc++.h>
using namespace std;
double P;
double f(double x) {
return x + P / pow(2, x / 1.5);
}
int main() {
cin >> P;
double gold = (1 + sqrt(5)) / 2;
double l = 0, r = P;
double c1 = (l * gold + r) / (1 + gold);
double c2 = (l + r * gold) / (1 + gold);
double f_c1 = f(c1);
double f_c2 = f(c2);
while (r - l > 0.00000001) {
if (f_c1 > f_c2) {
l = c1;
c1 = c2;
f_c1 = f_c2;
c2 = (l * gold + r) / (1 + gold);
f_c2 = f(c2);
}
else {
r = c2;
c2 = c1;
f_c2 = f_c1;
c1 = (l + r * gold) / (1 + gold);
f_c1 = f(c1);
}
}
cout << fixed << setprecision(10) << f(l) << endl;
}
2.8798910904
0.0400000000
447213595499958336.0000000000
#include <bits/stdc++.h>
using namespace std;
double P;
double f(double x) {
return x + P / pow(2, x / 1.5);
}
int main() {
cin >> P;
double l = 0, r = P;
while (r - l > 0.00000001) {
double c1 = (2 * l + r) / 3;
double c2 = (l + 2 * r) / 3;
if (f(c1) > f(c2)) l = c1;
else r = c2;
}
cout << fixed << setprecision(10) << f(l)<< endl;
}
自分は 黄金分割探索 をよく知りませんが、↓こちらの記事を参考に書き換えてみました。
double c1 = (l * gold + r) / (1.0 + gold);
double c2 = (l + r * gold) / (1.0 + gold);
どうして初回とそれ以降とで計算式を変えてしまったのでしょうか。
#include <bits/stdc++.h>
using namespace std;
double P;
double f(double x) {
return x + P / pow(2, x / 1.5);
}
int main() {
cin >> P;
double gold = (1 + sqrt(5)) / 2;
double l = 0, r = P;
double c1 = (l * gold + r) / (1 + gold);
double c2 = (l + r * gold) / (1 + gold);
double f_c1 = f(c1);
double f_c2 = f(c2);
while (r - l > 0.00000001) {
if (f_c1 > f_c2) {
l = c1;
c1 = c2;
f_c1 = f_c2;
- c2 = (l * gold + r) / (1 + gold);
+ c2 = (l + r * gold) / (1 + gold);
f_c2 = f(c2);
}
else {
r = c2;
c2 = c1;
f_c2 = f_c1;
- c1 = (l + r * gold) / (1 + gold);
+ c1 = (l * gold + r) / (1 + gold);
f_c1 = f(c1);
}
}
cout << fixed << setprecision(10) << f(l) << endl;
}
@pomodoro_
Questionerありがとうございます!!!
全然気付けなくて困っていました。ACできました!